The present invention relates generally to intercepting and processing packets that are related to a connection. More specifically, finding a connection object containing information related to the connection by looking once in a hash table that contains entries for packets sent in both directions between two parties is described.
Various network appliances are used in networks to intercept packets and process packets. These appliances include load balancers, network address translation (NAT) devices, proxies, firewalls, and packet monitors. These devices monitor or modify packets on a network. In many cases, packets belonging to different connections are treated differently. Often, packets corresponding to different flows in the same connection are handled differently.
Instructions for handling packets in different flows are stored by the network appliance for the purpose of determining how to handle incoming packets. These instructions must be accessed quickly so that packet processing is not unduly delayed. FIG. 1A is a block diagram illustrating a network that includes a client 102, a network appliance 104, and a set of servers 106. For the purpose of this illustration, network appliance 104 will be described as a NAT device that translates the destination address of certain packets sent from the client to a global IP address assigned to the group of servers. Network appliance 104 translates the global IP address used by the client to the local IP address of one of the servers selected to handle the connection with the client. The client IP address and port are referred to as the foreign IP address and port.
The network appliance modifies certain packets or records certain packets that belong to certain connections. A connection is made up of two flows, one in each direction between two parties. In general, a source address and port number, a destination address and port number, and a protocol define a flow. The source and destination addresses and ports are reversed for flows in opposite directions. For the purpose of illustration, this specification describes an example using only addresses as flow identifiers. It should be noted, whenever only an address is mentioned as an identifier, that an address and port may also be used and that a protocol may be added in some embodiments as well.
In the example shown in FIG. 1A, each connection is defined by a client IP address and port, a local IP address and port corresponding to the server selected to handle the connection, and a global IP address and port that corresponds to the IP address and port specified by the client for the connection. Packets passing through the network appliance are handled differently depending on whether they are a part of the flow from the client to the server or the flow from the server to the client. Therefore, network appliance 104 must, for each packet received, find a connection object that corresponds to the connection to which the packet belongs and also determine whether the packet is an incoming or an outgoing packet. For the purpose of this description, the terms incoming and outgoing are defined with reference to the server.
FIG. 1B is a block diagram illustrating the components of a typical network appliance. A processor 110 is connected to a memory 112 and several inbound/outbound interfaces that allow the network appliance to send and receive packets. FIG. 1B shows an inbound interface 114 and an outbound interface 116. Each of the interfaces are intended to represent a large number of interfaces. In some embodiments, the inbound/outbound interfaces are distinguished by whether they are on the client side or the server side. The network appliance may be implemented on any suitable general purpose computer architecture, including a machine running UNIX or Microsoft Windows.
FIG. 2A is a chart illustrating which address is included as the source and destination address for inbound and outbound packets. For an inbound packet, the foreign address is the source address and the global address is the destination address. For an outbound packet, the foreign address is the destination address and the local address is the source address. The foreign address is included in both inbound and outbound packets as either the source address or the destination address. As a result, a connection object that corresponds to a packet can be located by hashing only the foreign address included in the connection object. A match in the hash table that corresponds to the connection object can be located by first searching using the source address of the packet and then searching using the destination address of the packet. If the connection object is found using the source address of the packet, then the packet is an inbound packet that includes the foreign address of the connection as its source address. If the search using the packet destination address locates the connection object, then the packet is an outbound packet and the foreign address of the connection is the destination address of the outbound packet. Thus, two lookups are required at most to locate a hash table entry that corresponds to the correct connection object.
FIG. 2B is a flowchart illustrating a process for creating a new entry in a hash table for a new connection object. The process starts at 220. In a step 222, the foreign IP address of the connection objects is hashed. Next, in a step 224, the hash is used to index into the hash table. In a step 226, the pointer from the hash table is copied into the new connection object. Then, in a step 228, a pointer to the new connection object is written into the hash table. The process ends at 230.
FIG. 2C is a flow chart illustrating a process for searching for a connection object when a packet is received. The process starts at 240. In a step 242, the packet source IP address is hashed. Then, in a step 244, the hash list is checked to see if the source IP address hash is included in the list. If the source IP address hash is found, then in step 246, it is determined that the packet is an inbound packet. In a step 247, the connection object is retrieved and the process ends at 254.
If, in step 244, the source IP address hash is not found, then control is transferred to a step 248. In step 248, the packet destination IP address is hashed and the hash list is checked again. If the destination IP address hash is not found, then control is transferred to a step 250 and it is determined that no connection object exists. If the destination IP address hash is found, then control is transferred to a step 252 and it is determined that the packet is an outbound packet. Control is then transferred to step 247 and the connection object is retrieved. Thus, the connection object is retrieved and it is determined whether the packet is an inbound packet or an outbound packet.
FIG. 2D is a block diagram illustrating a hash table and several connection objects which may be searched using the hash table. Hash table 266 includes a hash 268. Hash 268 includes a pointer to a connection object 272. Connection object 272 points to connection object 274, which points to connection object 276. The pointer to connection object 272 was entered in the hash table using a process such as is described in FIG. 2B. The foreign IP address in connection object 272, as well as connection objects 274 and 276 hashes to hash 268. Connection object 276 is the last connection object in the hash chain and so it contains a null pointer.
FIG. 2E is a block diagram illustrating hash table 266 just before connection object 272 is inserted in the hash table. Hash 268 includes a pointer labeled xe2x80x9cAxe2x80x9d that points to connection object 274. Connection object 274 includes a pointer labeled xe2x80x9cBxe2x80x9d that points to connection object 276. Connection object 272 is inserted by copying pointer A into connection object 272 and then overwriting pointer A in hash table 266 with a pointer to connection object 272. Pointer B in connection object 274 remains unchanged. Thus, connection object 272 is inserted at the beginning of the hash chain associated with hash 268.
When addresses are described as being hashed and used to find a connection object, more than one connection object may correspond to a set of addresses because different ports may be used for different connections between those addresses. The one connection object that matches a packet can be determined by examining the port numbers in a set of connection objects identified using the hash table. Alternatively, port numbers can be included in identifiers before hashing so that connection objects with different ports are not retrieved together. In general, the term flow identifier is used to describe any information in a connection object used to find the flows belonging to the connection object. The term packet identifier is used to describe any information in a packet header that is used to find the connection or flow corresponding to the packet. In the example described herein, the identifiers are combinations of IP addresses.
It would be useful if the lookup process for connection objects could be simplified and sped up for incoming packets. Since a very large number of packets is likely to be received for a given connection, the resources of the network appliance may be taxed as the lookup process is executed many times. Maximizing the efficiency of the lookup process would result in reduced latency in the network appliance.
Accordingly, a method is described for storing a connection object using a hash table and then finding the connection object that corresponds to a packet in a flow with a single lookup. Each connection object is hashed twicexe2x80x94once in each direction relative to a virtual server. For inbound packets, the foreign and global addresses are hashed, since those addresses correspond to the source and destination addresses of incoming packets. For outbound packets, the local and foreign addresses are hashed, since those addresses correspond to the source and destination addresses of outgoing packets. Two pointers, one for each hash, are entered in a hash table used to search for a connection object. The inbound and outbound hash table entries point to memory locations that contain information about whether the packet matching the hash table entry is inbound or outbound. The memory location may be part of a connection object or may point to a connection object. Thus, the connection object corresponding to a packet may be found by hashing the source and destination addresses of the packet and doing a single lookup in the hash table that contains hashes in both directions for each connection object.
It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, a method, or a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or electronic communication links. Several inventive embodiments of the present invention are described below.
In one embodiment, a method of storing and retrieving instructions for handling a packet corresponding to a connection includes hashing an incoming flow identifier for incoming packets to obtain an incoming hash and hashing an outgoing flow identifier for outgoing packets to obtain an outgoing hash. An incoming entry corresponding to the incoming hash is inserted in a bidirectional hash table and an outgoing entry corresponding to the outgoing hash is inserted in the bidirectional hash table. A packet identifier is hashed to obtain a packet hash and a matching entry in the bidirectional hash table is determined that corresponds to the packet hash.
In one embodiment, a network appliance configured to store and retrieve instructions for handling a packet corresponding to a connection includes a connection storing processor configured to hash an incoming flow identifier for incoming packets to obtain an incoming hash; to hash an outgoing flow identifier for outgoing packets to obtain an outgoing hash; to insert an incoming entry corresponding to the incoming hash in a bidirectional hash table; and to insert an outgoing entry corresponding to the outgoing hash in a bidirectional hash table. A connection finding processor is configured to hash a packet identifier to obtain a packet hash; and to determine a matching entry in the bidirectional hash table that corresponds to the packet hash. A memory is configured to store the bidirectional hash table.
In one embodiment, a computer readable medium includes program code for storing and retrieving information for handling a packet corresponding to a connection. The program code comprising instructions for hashing an incoming flow identifier for incoming packets to obtain an incoming hash and hashing an outgoing flow identifier for outgoing packets to obtain an outgoing hash. An incoming entry corresponding to the incoming hash is inserted in a bidirectional hash table and an outgoing entry corresponding to the outgoing hash is inserted in the bidirectional hash table. A packet identifier is hashed to obtain a packet hash and a matching entry in the bidirectional hash table is determined that corresponds to the packet hash.
These and other features and advantages of the present invention will be presented in more detail in the following detailed description and the accompanying figures which illustrate by way of example the principles of the invention.